
 class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

 class Solution143 {
     public void reorderList(ListNode head) {
         if(head == null || head.next == null) return ;
         // 1. 把链表分成两半
         ListNode slow = head ;
         ListNode fast = head ;
         while(fast != null && fast.next != null){
             slow = slow.next ;
             fast = fast.next.next ;
         }
         // 分成两半
         ListNode cur1 = head ;
         while(cur1 .next != slow){
             cur1 = cur1.next ;
         }
         cur1.next = null ;

         // 2. 把 后面的 一半逆序过来
         ListNode h2 = slow , cur2 = slow.next;
         h2.next = null ;
         while(cur2 != null){
             ListNode cur2Next = cur2.next ;
             cur2.next = h2 ;
             h2 = cur2 ;
             cur2 = cur2Next ;
         }

         // 3. 合并两个链表
         ListNode last = head ;
         cur1 = head.next ; cur2 = h2 ;
         while(cur1 != null && cur2 != null){
             last.next = cur2 ;
             cur2 = cur2.next ;
             last = last.next ;
             last.next = cur1 ;
             cur1 = cur1.next ;
             last = last.next ;
         }
         while(cur1 != null){
             last.next = cur1 ;
             cur1 = cur1.next ;
             last = last.next ;
         }
         while(cur2 != null){
             last.next = cur2 ;
             cur2 = cur2.next ;
             last = last.next ;
         }



     }
 }